import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1().maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(new Solution1().maxSlidingWindow(new int[]{1}, 1)));
    }
}


//官方题解2：单调队列，使用双端队列
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int ansSize = nums.length - k + 1;
        if (ansSize <= 0) {
            return new int[0];
        }
        int[] ans = new int[ansSize];

        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        ans[0] = nums[deque.peek()];
        for (int l = 1; l < ansSize; l++) {
            int h = l + k - 1;
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[h]) {
                deque.pollLast();
            }
            deque.offerLast(h);

            if (deque.peek() < l) {
                deque.poll();
            }
            ans[l] = nums[deque.peek()];
        }

        return ans;
    }
}

//官方题解3：分块+预处理，先得到prefixMax和suffixMax数组
class Solution1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] prefixMax = new int[nums.length];
        int[] suffixMax = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i == nums.length - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int ansSize = nums.length - k + 1;
        int[] ans = new int[ansSize];
        for (int i = 0; i < ansSize; i++) {
            ans[i] = Math.max(prefixMax[i + k - 1], suffixMax[i]);
        }
        return ans;
    }
}


//官方题解1修改：PriorityQueue中只存储索引，不存储值
//注意：PriorityQueue remove(Object)的复杂度为O(n)，不能满足时间要求。
class Solution2_1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int ansLen = nums.length - k + 1;
        if (ansLen <= 0) {
            return new int[]{};
        }

        int[] ans = new int[ansLen];
        Queue<Integer> window = new PriorityQueue<>((o1, o2) -> nums[o2] - nums[o1]);

        for (int i = 0; i < k; i++) {
            window.add(i);
        }

        ans[0] = nums[window.peek()];

        for (int i = 1; i < ansLen; i++) {
            int j = i + k - 1;
            window.add(j);
            while (window.peek() < i) {
                window.poll();
            }

            ans[i] = nums[window.peek()];
        }

        return ans;
    }
}


//官方题解1
//注意：PriorityQueue remove(Object)的复杂度为O(n)，不能满足时间要求。
class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int ansLen = nums.length - k + 1;
        if (ansLen <= 0) {
            return new int[]{};
        }

        int[] ans = new int[ansLen];
        Queue<int[]> window = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1]);

        for (int i = 0; i < k; i++) {
            window.add(new int[]{nums[i], i});
        }
        assert window.peek() != null;
        ans[0] = window.peek()[0];

        for (int i = 1; i < ansLen; i++) {
            int j = i + k - 1;
            window.add(new int[]{nums[j], j});
            while (true) {
                assert window.peek() != null;
                if (!(window.peek()[1] < i)) break;
                window.poll();
            }
            assert window.peek() != null;
            ans[i] = window.peek()[0];
        }

        return ans;
    }
}
